#include<vector>
class Solution {
public:
    std::vector < long > ss;
    long sum = 0l;
    int halveArray(std::vector<int>& nums) {
        ss.resize(nums.size());
        for (int i = 0; i < nums.size(); i++) {
            ss[i] = 0l;
        }
        updateFromButtomToTop(nums);
        long nowSum = sum;
        int flag = 0;
        int n = nums.size();
        while (nowSum>sum/2) {
            nowSum -= ss[0]/2;
            ss[0] /= 2;
            flag++;
            updateToEnd(ss, 0,n);    
        }
        return flag;
    }

    void updateFromButtomToTop(std::vector<int>& nums) {
        int n = nums.size()-1;
        while (n >= 0) {
            ss[n] = (long)nums[n] << 20 ;
            sum += ss[n];
            updateToEnd(ss, n,nums.size());
            n--;
        }
    }
    void updateToEnd(std::vector<long>& nums, int index,int n) {
        int lindex = index * 2 + 1;
        int nowIndex =index;
        while (lindex < n)
        {
        int rindex = lindex + 1;
        int maxIndex = rindex<n && nums[rindex]> nums[lindex] ? rindex : lindex;
        if (nums[maxIndex] <= nums[nowIndex])
            return;
        swap(nums[maxIndex], nums[nowIndex]);
        nowIndex = maxIndex;
        lindex = nowIndex * 2 + 1;
    }
    }
    void swap(long& a, long& b) {
        long m = a;
         a = b;
         b = m;
    }
};

